/**
 * @author SaoE
 * @date 2025/3/3 20:15
 */
public class _416 {
    public boolean canPartition(int[] nums) {
        int target = 0, sum = 0;
        for(int num : nums){
            sum += num;
        }
        if(sum % 2 != 0) {
            return false;
        }
        target = sum / 2;
        int[] dp = new int[target + 1];
        dp[0] = 0;
        // 如果使用一维dp数组，物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒序遍历！
        for(int i = 0; i < nums.length; i++){
            for(int j = target; j >= nums[i]; j--){
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
                // System.out.println(dp[j]);
            }
            if(dp[target] == target) {
                return true;
            }
        }
        return false;
    }
}
